/* 1200012773
   胡树伟
   */

/* 诚实代码保证：
   我真诚地保证：
   我自己独立地完成了整个程序从分析、设计到编码的所有工作。
   如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
   详细地列举我所遇到的问题，以及别人给我的提示。
   在此，我感谢 党和国家 对我的启发和帮助。下面的报告中，我还会具体地提到
   他们在各个方法对我的帮助。
   我的程序里中凡是引用到其他程序或文档之处，
   例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
   我都已经在程序的注释里很清楚地注明了引用的出处。
   我从未抄袭过别人的程序，也没有盗用别人的程序，
   不管是修改式的抄袭还是原封不动的抄袭。
   我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
   */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>

typedef int item_t;
typedef unsigned long hashkey_t;
#define countbits __builtin_popcountl

item_t *itembuf = NULL; /* 所有项集 */
int itembuf_size = 0;
int *pos = NULL; /* 交易标号 */
int pos_size = 0;
int ndeals;
int qflag = 0;
int total = 0;

double perc;

double pct;
int threshold;

struct items_t {
	int kitems;
	int hashcnt;
	item_t *items;
	hashkey_t *hash;
} ;

struct cand_t {
	int n;
	int size;
	struct items_t **items;
} ;

#define HASH_KEYSZ (sizeof(((struct items_t *)NULL)->hash[0])*8)
#define HASH_NKEYS ((ndeals-1)/HASH_KEYSZ+1)

int enough (int k) { /*{{{*/
	return k >= threshold;
}
/*}}}*/
void usage () { /*{{{*/
	fprintf (stderr, "usage: ./mine 0.3 <data >result\n");
	exit(1);
}
/*}}}*/
void readargs (int argc, char *argv[]) { /*{{{*/
	if (argc != 2 && argc != 3)
		usage ();

	int tres = sscanf (argv[1], "%lf", &perc);
	if (!(tres == 1 &&perc >= 0 && perc <= 1))
		usage ();
	if (argc == 3) {
		if (!strcmp (argv[2], "-q"))
			qflag = 1;
		else
			usage ();
	}
}
/*}}}*/
int cmp_int (const void *a, const void *b) { /*{{{*/
	return *(int*)a - *(int*)b;
}
/*}}}*/
int cmp_item (const void *a, const void *b) { /*{{{*/
	return itembuf[*(int*)a] - itembuf[*(int*)b];
}
/*}}}*/
int getnum () { /*{{{*/
	int ch;
	do {
		ch = getchar ();
	} while (isspace(ch) && ch != '\n');

	if (ch == EOF || ch == '\n')
		return -1;

	int k = 0;
	do {
		assert (isdigit(ch));
		k = k * 10 + (ch - '0');
		ch = getchar ();
	} while (isdigit (ch));

	int tres = ungetc (ch, stdin);
	((void)tres);
	assert (tres != EOF);

	return k;
}
/*}}}*/
void putnum (int k) { /*{{{*/
	static char buf[31];
	char *p = buf + sizeof(buf) - 1;
	*p = '\0';
	for (; k; k /= 10) {
		*--p = k % 10 + '0';
		assert (p > buf);
	}
	fputs (p, stdout);
}
/*}}}*/
#define append_element(element, pointer, _n, size) /*{{{*/ \
	do {\
		typeof(_n) n = (_n);\
		assert (n <= (size));\
		if (n == (size)) {\
			(size) = ((size) + !(size)) << 1;\
			(pointer) = realloc ((pointer), (size)*(sizeof(element)));\
			assert ((pointer) != NULL);\
		}\
		assert (n < (size));\
		(pointer)[n] = (element);\
	} while (0)
/*}}}*/
void loaddata () { /*{{{*/
	int k, l, r = 0;
	ndeals = 0;

	while ((k=getnum()) >= 0) {
		l = r;
		do {
			append_element (k, itembuf, r++, itembuf_size);
		} while ((k=getnum()) >= 0);

		qsort (itembuf + l, r - l, sizeof(*itembuf), cmp_int);
		append_element (l, pos, ndeals++, pos_size);
	}

	append_element (r, pos, ndeals, pos_size);
	threshold = (int)(ndeals * perc);
}
/*}}}*/
void printdata () { /*{{{*/
	puts ("data:");
	for (int i = 0; i < ndeals; ++i) {
		printf ("deal %d: ", i);
		for (int j = pos[i]; j < pos[i+1]; ++j) {
			printf ("%d ", itembuf[j]);
		}
		puts ("");
	}
}
/*}}}*/
void clean () { /*{{{*/
	free (itembuf);
	itembuf_size = 0;
	free (pos);
	pos_size = 0;
}
/*}}}*/
int lbound (int key, int data[], int n) { /*{{{*/
	int l = 0, r = n - 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (key >= data[m])
			l = m + 1;
		else
			r = m - 1;
	}

	assert (r >= 0);
	assert (r < n);
	assert (key >= data[r]);
	assert (data[r+1] > key);
	return r;
}
/*}}}*/

struct items_t *new_items (int kitems) { /*{{{*/
	struct items_t *items = malloc (sizeof(*items));
	items->kitems = kitems;
	items->items = malloc (kitems * sizeof(items->items[0]));
	assert (ndeals > 0);
	items->hashcnt = 0;
	items->hash = calloc (HASH_NKEYS, HASH_KEYSZ);
	return items;
}
/*}}}*/
int combiny (const struct items_t *items_a, const struct items_t *items_b) { /*{{{*/
	assert (items_a->kitems == items_b->kitems);
	int kitems = items_a->kitems, i;
	assert (kitems > 0);
	for (i = 0; i < kitems - 1; ++i)
		if (items_a->items[i] != items_b->items[i])
			return 0;
	assert (items_a->items[i] != items_b->items[i]);
	return 1;
}
/*}}}*/
void items_setdeal (struct items_t *items, int keypos) { /*{{{*/
	assert (keypos < ndeals);
	assert (!(items->hash[keypos/HASH_KEYSZ] & ((hashkey_t)1 << (keypos%HASH_KEYSZ))));
	++items->hashcnt;
	items->hash[keypos/HASH_KEYSZ] |= (hashkey_t)1 << (keypos%HASH_KEYSZ);
}
/*}}}*/
void combine_items (struct items_t *dst, const struct items_t *items_a, const struct items_t *items_b) { /*{{{*/
	assert (items_a->kitems == items_b->kitems);
	int kitems = items_a->kitems;
	assert (kitems > 0);

	dst->kitems = kitems + 1;
	free (dst->items);
	dst->items = malloc (dst->kitems * sizeof(dst->items[0]));
	memcpy (dst->items, items_a->items, kitems * sizeof(dst->items[0]));
	dst->items[kitems] = items_b->items[kitems-1];
}
/*}}}*/
void combine_hash (struct items_t *dst, const struct items_t *items_a, const struct items_t *items_b) { /*{{{*/
	int cnt0 = 0, cnt1 = 0, cnt2 = 0, cnt3 = 0;
#define CALC_HASH(x) \
	do {\
		dst->hash[i+(x)] = items_a->hash[i+(x)] & items_b->hash[i+(x)];\
		cnt##x += countbits (dst->hash[i+(x)]);\
	} while (0)

	int i;
	for (i = 0; i+4 <= HASH_NKEYS; i+=4) {
		CALC_HASH (0);
		CALC_HASH (1);
		CALC_HASH (2);
		CALC_HASH (3);
	}

	if (i+0 < HASH_NKEYS) CALC_HASH(0);
	if (i+1 < HASH_NKEYS) CALC_HASH(1);
	if (i+2 < HASH_NKEYS) CALC_HASH(2);
#undef CALC_HASH

	dst->hashcnt = cnt0 + cnt1 + cnt2 + cnt3;
}
/*}}}*/
void release_items (struct items_t *items) { /*{{{*/
	free (items->items);
	items->items = NULL;
	free (items->hash);
	items->hash = NULL;
	free (items);
}
/*}}}*/
void output_items (struct items_t *items) { /*{{{*/
	for (int i = 0; i < items->kitems; ++i) {
		putnum (items->items[i]);
		putchar (' ');
	}
	fputs (": ", stdout);
	putnum (items->hashcnt);
	putchar ('\n');
}
/*}}}*/

void init_cand (struct cand_t *cand) { /*{{{*/
	cand->n = 0;
	cand->size = 0;
	cand->items = NULL;
}
/*}}}*/
void add_cand (struct cand_t *cand, struct items_t *items) { /*{{{*/
	append_element (items, cand->items, cand->n++, cand->size);
}
/*}}}*/
void clear_cand (struct cand_t *cand) { /*{{{*/
	cand->n = 0;
}
/*}}}*/
void release_cand_items (struct cand_t *cand) { /*{{{*/
	for (int i = 0; i < cand->n; ++i) {
		release_items (cand->items[i]);
		cand->items[i] = NULL;
	}

	cand->n = 0;
}
/*}}}*/
void release_cand (struct cand_t *cand) { /*{{{*/
	release_cand_items (cand);
	free (cand->items);
	cand->items = NULL;
}
/*}}}*/
void output_cand (struct cand_t *cand) { /*{{{*/
	for (int i = 0; i < cand->n; ++i) {
		output_items (cand->items[i]);
	}
}
/*}}}*/

void process () { /*{{{*/
	void search_multi ();
	struct cand_t cand;
	init_cand (&cand);

	/* single item */
	{
		int *t_item = malloc (pos[ndeals] * sizeof(*t_item));
		for (int i = 0; i < pos[ndeals]; ++i)
			t_item[i] = i;
		qsort (t_item, pos[ndeals], sizeof(*t_item), cmp_item);
		int i, p;

		for (i = 0; i < pos[ndeals]; i = p) {
			for (p = i; p < pos[ndeals] && itembuf[t_item[i]] == itembuf[t_item[p]]; ++p)
				;
			if (!enough (p-i))
				continue;

			struct items_t *items = new_items (1);

			items->items[0] = itembuf[t_item[i]];
			for (int j = i; j < p; ++j) {
				items_setdeal (items, lbound (t_item[j], pos, ndeals));
			}

			add_cand (&cand, items);
		}

		free (t_item);
	}

	search_multi (&cand);
	release_cand (&cand);
}

void search_multi (struct cand_t *cand) {
	if (cand->n == 0)
		return;

	if (!qflag)
		output_cand (cand);
	total += cand->n;

	struct cand_t new_cand;
	init_cand (&new_cand);

	struct items_t *items = new_items (0);
	for (int i = 0; i < cand->n; ++i) {
		clear_cand (&new_cand);

		for (int j = i+1; j < cand->n; ++j) {
			assert (combiny (cand->items[i], cand->items[j]));
			combine_hash (items, cand->items[i], cand->items[j]);
			if (enough (items->hashcnt)) {
				combine_items (items, cand->items[i], cand->items[j]);
				add_cand (&new_cand, items);
				items = new_items (0);
			}
		}

		search_multi (&new_cand);
		release_cand_items (&new_cand);
		clear_cand (&new_cand);
	}

	release_items (items);
	release_cand (&new_cand);
}
/*}}}*/

int main (int argc, char *argv[]) {
	readargs (argc, argv);
	loaddata ();
	process ();
	clean ();

	if (qflag)
		printf ("%d\n", total);
	return 0;
}
